FIGS. 37A to 37D are figures illustrated in Patent Literature 1, and show a method for configuring hardware to detect, from a given character string, a character string that matches a regular expression. FIGS. 37A to 37D illustrate four configuration patterns for converting basic operators of regular expressions into hardware.
For example, a character string (a|b)*c described by a regular expression represents such a character string that the sum of “a” and “b” (which means that at least one of “a” and “b” is included) is repeated 0 or more times and then “c” follows. Accordingly, for a character string abcdefgh, for example, a character string abc matches the character string described by the regular expression described above.
In the case of converting this regular expression into a circuit, “a”, “b”, and “c” are first replaced by a character comparison shown in FIG. 37A, i.e., a circuit for detecting whether or not to correspond to each character. Next, a|b connects a sum shown in FIG. 37B, i.e., a circuit for character comparison with “a” and a circuit for character comparison with “b”, according to a pattern using a logical OR. Then, (a|b)* connects a repetition shown in FIG. 37D, i.e., a circuit using a|b as a basic unit, according to a predetermined pattern. Lastly, (a|b)*c connects a concatenation shown in FIG. 37C, i.e., connects in series the circuit of (a|b)* shown in FIG. 37D and a circuit using a circuit for character comparison with “c” as a basic unit. As described above, the connection of the character comparison circuits according to the predetermined pattern by using each character comparison circuit as a basic unit makes it possible to systematically convert any regular expression into a circuit.
The character string matching circuit described above is illustrated by way of example. A device that determines whether specific functions are called in a specific order by use of regular expressions is also disclosed in Patent Literature 2, for example.
Further, Non Patent Literature 1 proposes a circuit for detecting an event sequence, which satisfies a specific condition, from a large number of events, by using a specific language different from a function type. Furthermore, Non Patent Literature 2 proposes a circuit for implementing operators of regular expressions that express a repetition.